package leetcode.editor.cn;

import java.util.ArrayDeque;
import java.util.Stack;

class RemoveAllAdjacentDuplicatesInString {
    public static void main(String[] args) {
        Solution solution = new RemoveAllAdjacentDuplicatesInString().new Solution();
        solution.removeDuplicates("abbaca");
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * 使用栈
         *
         * @param s
         * @return
         */
        /*
        public String removeDuplicates(String s) {
            Stack<Character> stack = new Stack<>();
            char ch;
            for (int i = 0; i < s.length(); i++) {
                ch = s.charAt(i);
                if (!stack.isEmpty()) {
                    char temp = stack.peek();
                    // 相等即出栈
                    if (ch == temp) {
                        stack.pop();
                    } else {
                        // 不相等即入栈
                        stack.push(ch);
                    }
                } else {
                    // 栈为空直接入栈
                    stack.push(ch);
                }
            }

            // 将栈转化为字符串
            String str = "";
            while (!stack.isEmpty()) {
                str = stack.pop() + str;
            }

            return String.valueOf(str);
        }
         */

        /**
         * 双指针法
         *
         * @param s
         * @return
         */
        /*public String removeDuplicates(String s) {
            int fast = 0, slow = 0;
            char[] chars = s.toCharArray();
            while (fast < s.length()) {
                // 直接用fast指针覆盖slow指针的值
                chars[slow] = chars[fast];
                // 存在相邻相等的元素，slow减一，不用减二，slow会被下次循环覆盖
                if (slow > 0 && chars[slow] == chars[slow - 1]) {
                    slow--;
                } else {
                    slow++;
                }
                fast++;
            }

            return String.valueOf(chars, 0, slow);
        }*/


        /**
         * 使用ArrayDeque作为栈
         *
         * @param s
         * @return
         */
        /*public String removeDuplicates(String s) {
            Stack<Character> stack = new Stack<>();
            for (int i = 0; i < s.length(); i++) {
                if (stack.isEmpty() || stack.peek() != s.charAt(i)) {
                    stack.push(s.charAt(i));
                } else {
                    stack.pop();
                }
            }

            String str = "";
            while (!stack.isEmpty()) {
                str = stack.pop() + str;
            }

            return str;
        }*/

        /**
         * 双指针法
         *
         * @param s
         * @return
         */
        /*public String removeDuplicates(String s) {
            int slow = 0;
            int fast = 0;
            char[] array = s.toCharArray();

            while (fast < array.length) {
                array[slow] = array[fast];
                if (slow > 0 && array[slow] == array[slow - 1]) {
                    slow--;
                } else {
                    slow++;
                }
                fast++;
            }

            String str = String.valueOf(array);
            return str.substring(0, slow);
        }*/
        public String removeDuplicates(String s) {
            Stack<Character> stack = new Stack<>();
            for (int i = 0; i < s.length(); i++) {
                char c = s.charAt(i);
                if (!stack.isEmpty() && stack.peek() == c) {
                    stack.pop();
                } else {
                    stack.push(c);
                }
            }

            char[] res = new char[stack.size()];
            int i = stack.size() - 1;
            while (!stack.isEmpty()) {
                res[i--] = stack.pop();
            }

            return new String(res);
        }

    }
//leetcode submit region end(Prohibit modification and deletion)

}
